package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午5:19:21
*/
public class Q14 {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int first = -1;
        int left = 0;
        int right = nums.length - 1;
        int point = -1;
        while (left <= right) {
            point = (right + left) / 2;
            if (nums[point] > target) {
                right = point - 1;
            } else if (nums[point] == target) {
                first = point;
                right = point - 1;
            } else {
                left = point + 1;
            }
        }
        return first;
    }

    @Test
    public void testA() {
        int[] nums = { 1, 2, 2, 3, 3, 3, 3, 4, 5, 10 };
        int target = 3;
        System.out.println(binarySearch(nums, target));
    }
}
